<!DOCTYPE html>
<html lang="zh">
    <head>
  <!-- 元数据 -->
  <meta charset="utf-8">
  
  
  <title>进程同步与互斥（操作系统笔记5） | 舛羽的笔记小站</title>
  <meta name="author" content="cy" />
  <meta http-equiv="Cache-Control" content="no-transform" />
  <meta http-equiv="Cache-Control" content="no-siteapp" />
  <meta http-equiv="X-UA-Compatible" content="IE=edge" />
  <meta name="robots" content="index,follow" />
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
  <meta name="format-detection" content="telphone=no, email=no" />
  
    <meta name="keywords" content="操作系统" />
  
  <meta name="description" content="本篇笔记将介绍一下进程的同步与互斥，由于进程的异步性会产生非常多的包括死锁等问题。本章主要讲述如何处理或解决这些问题。">
<meta property="og:type" content="article">
<meta property="og:title" content="进程同步与互斥（操作系统笔记5）">
<meta property="og:url" content="http://example.com/2023/01/04/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0-5/index.html">
<meta property="og:site_name" content="舛羽的笔记小站">
<meta property="og:description" content="本篇笔记将介绍一下进程的同步与互斥，由于进程的异步性会产生非常多的包括死锁等问题。本章主要讲述如何处理或解决这些问题。">
<meta property="og:locale">
<meta property="og:image" content="https://s2.loli.net/2023/01/04/WZHM1DObSBePoXx.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/04/DY6NKd8xjkeaT4O.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/04/yU67XpsZgwimQSW.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/04/9edIMwRyWZqb3mo.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/04/DIKnGZQ9gOLVvJS.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/04/s1QYvLt6a3HWuf8.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/04/AldfWkLJTZiMDGh.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/04/p7fUPIsZdOy1g8t.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/04/ZiRtLB1FISMmzYo.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/04/24VIRFjcCMeGvYD.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/04/TyZfjb3hCmvzlaP.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/09/C8hQdRY4UL7eigr.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/09/WoVeiuNvMw7d38Q.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/09/TB4f6OmlFDVN2de.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/09/P4HjFV7JWiwD9BE.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/10/xqMaI8vho67Ufcy.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/10/9vuaDQBlNnobxYf.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/10/nckNgCZfO7IJAe4.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/10/PdFxtjOT2ArKGas.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/10/7dHPFQfpusAtmSk.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/10/oJflm3bgO4NkETu.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/11/w2NzyafVkEqpK5T.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/11/UCA2NelyHbXrZFj.png">
<meta property="og:image" content="c:\Users\cy\Desktop\20200326231222488.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/11/HxITMzfacEXBUZ1.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/11/hGCe1DOrUTPnMou.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/11/lEKrkThLjiwIvCd.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/11/8IAYbga5cJrKDey.png">
<meta property="og:image" content="https://s2.loli.net/2023/01/11/H4vQGZbNcLpEPVK.png">
<meta property="article:published_time" content="2023-01-04T07:47:47.000Z">
<meta property="article:modified_time" content="2023-02-13T06:16:33.855Z">
<meta property="article:author" content="cy">
<meta property="article:tag" content="操作系统">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://s2.loli.net/2023/01/04/WZHM1DObSBePoXx.png">
  
  <!-- 站点验证相关 -->
  
    
    
    
  
  <!-- 样式表文件 -->
  <link rel="stylesheet" id="kratos-css" href="/css/kratosr.min.css" media="all"></script>
  
    <link rel="stylesheet" id="darkmode-css" href="/css/kr-color-dark.min.css" media="(prefers-color-scheme: dark)"></script>
    <script src="/js/kr-dark.min.js"></script>
  
  
    <link rel="stylesheet" id="highlight-css" href="/css/highlight/night-eighties.min.css" media="all"></script>
  
  
  <link rel="stylesheet" id="fontawe-css" href="/vendors/font-awesome@4.7.0/css/font-awesome.min.css" media="all"></script>
  <link rel="stylesheet" id="nprogress-css" href="/vendors/nprogress@0.2.0/nprogress.css" media="all"></script>
  
  
  
    <link rel="stylesheet" href="/vendors/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css"></script>
  
  <!-- 不得不预先加载的一些JS文件 -->
  <script src="/vendors/jquery@3.6.0/dist/jquery.min.js"></script>
  
    <script src="/vendors/qrcode_js@1.0.0/qrcode.min.js"></script>
  
  
  <style>
    
      .kratos-cover.kratos-cover-2 {
        background-image: url('/images/banner.webp');
      }
    
    
      @media(min-width:768px) {
        body.custom-background {
          background-image: url('/images/bg.webp');
        }
      }
    
  </style>
  
<meta name="generator" content="Hexo 7.3.0"></head>


    <body class="custom-background">
        <div id="kratos-wrapper">
    <div id="kratos-page">
        <div id="kratos-header">
            <header id="kratos-desktop-topnav" class="kratos-topnav">
                <div class="container">
                    <div class="nav-header">
                        <nav id="kratos-menu-wrap">
                            <ul id="kratos-primary-menu" class="sf-menu">
                                
                                    
                                    
                                
                            </ul>
                        </nav>
                    </div>
                </div>
            </header>
            <header id="kratos-mobile-topnav" class="kratos-topnav">
                <div class="container">
                    <div class="color-logo"><a href="/">舛羽的笔记小站</a></div>
                    <div class="nav-toggle">
                        <a class="kratos-nav-toggle js-kratos-nav-toggle">
                            <i></i>
                        </a>
                    </div>
                </div>
            </header>
        </div>
        <div class="kratos-start kratos-hero-2">
            <!-- <div class="kratos-overlay"></div> -->
            <div class="kratos-cover kratos-cover-2 text-center">
                <div class="desc desc2 animate-box">
                    <a href="/">
                        <h2>舛羽的笔记小站</h2> <br />
                        <span></span>
                    </a>
                </div>
            </div>
        </div>

        <div id="kratos-blog-post">
            <div class="container">
                <div id="main" class="row">
                    

        

            <section class="col-md-8">

        

            <article itemscope itemtype="https://schema.org/Article">
    
    <link itemprop="mainEntityOfPage" href="http://example.com/2023/01/04/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0-5/">
    <div class="kratos-hentry kratos-post-inner clearfix">
        <header class="kratos-entry-header">
            
                <h1 class="kratos-entry-title text-center" itemprop="name headline">进程同步与互斥（操作系统笔记5）</h1>
            
            
            <ul class="kratos-post-meta text-center">
                <li><time datetime="2023-01-04T07:47:47.000Z" itemprop="datePublished"><i class="fa fa-calendar"></i> 2023-01-04</time></li>
                <li itemprop="author" itemscope itemtype="https://schema.org/Person">
                    <i class="fa fa-user"></i> 作者 <span itemprop="name">cy</span>
                </li>
                <li>
                    <i class="fa fa-edit"></i> 
                    
                    
                        ~5.27K
                    
                    字
                </li>
                
            </ul>
        </header>
        <div class="kratos-post-content">
            
            <div id="expire-alert" class="alert alert-warning hidden" role="alert">
                <div class="icon"><i class="fa fa-warning"></i></div>
                <div class="text"><p>本文最后编辑于 <time datetime="1676268993855"></time> 前，其中的内容可能需要更新。</p></div>
            </div>
            
            
            
            <hr />
            <div itemprop="articleBody"><p>本篇笔记将介绍一下进程的同步与互斥，由于进程的异步性会产生非常多的包括死锁等问题。本章主要讲述如何处理或解决这些问题。</p>
<span id="more"></span>
<h2 id="第五章-进程同步与互斥"><a href="#第五章-进程同步与互斥" class="headerlink" title="第五章 进程同步与互斥"></a>第五章 进程同步与互斥</h2><h3 id="5-1-进程同步与互斥"><a href="#5-1-进程同步与互斥" class="headerlink" title="5.1  进程同步与互斥"></a>5.1  进程同步与互斥</h3><ul>
<li>进程同步</li>
</ul>
<p>进程同步也被称为直接制约关系。</p>
<p>假设有两个进程他们有明确的先后执行的关系，但是因为操作系统的异步性，导致后执行的先执行造成程序错误就会得不偿失了，所以我们需要对后执行的进程加以制约确保他后执行。</p>
<p>例如，让系统计算1 + 2x3，假设系统产生两个进程: 一个是加法进程，一个是乘法进程。要让计算结果是正确的，一定要让加法进程发生在乘法进程之后,但实际上操作系统具有异步性,若不加以制约，加法进程发生在乘法进程之前是绝对有可能的，因此要制定一定的机制去约束加法进程，让它在乘法进程完成之后才发生。</p>
<ul>
<li>进程互斥</li>
</ul>
<p>进程互斥是一种间接制约的关系。</p>
<p>首先我们先介绍一个概念，<font color='red'>临界资源</font></p>
<p>我们把一个时间段内只允许一个进程使用的资源称为临界资源。（特别是物理设备，如摄像头、打印机）</p>
<p>对临界资源的访问一定要互斥的执行，还是拿打印机举个例子，你不能打印三国演义打着打着打西游记了吧，这下就真成四大名著合订本了。</p>
<p>对<font color='red'>临界资源的互斥访问</font>的<font color='red'>代码</font>可以分以下四块：</p>
<ul>
<li>进入区：负责检查是否可以使用资源，如果可以则要设置<font color='red'>有进程正在访问的标志</font></li>
<li>临界区：访问临界资源的那段代码</li>
<li>退出区：负责解除<font color='red'>有进程正在访问的标志</font></li>
<li>剩余区：做其他处理</li>
</ul>
<p>未来实现对临界资源的互斥访问，保证系统整体性能，需遵循四条规则：</p>
<ul>
<li>空闲让进：临界区空闲时，可以允许一个请求进入临界区</li>
<li>忙则等待：当已有进程进入临界区是，其他试图进入临界区的进程必须等待</li>
<li>有限等待：对请求访问的进程，应保证能在有限时间内进入临界区</li>
<li>让权等待：当进程不能进入临界区是，应立即释放处理机，防止忙等待（占着茅坑不拉屎）</li>
</ul>
<h3 id="5-2-软件实现互斥的方法"><a href="#5-2-软件实现互斥的方法" class="headerlink" title="5.2 软件实现互斥的方法"></a>5.2 软件实现互斥的方法</h3><p>这块我自己讲不清楚，就把别人文章中的截图粘贴过来了，图片均来自<a target="_blank" rel="noopener" href="https://blog.csdn.net/weixin_43914604/article/details/104943004">https://blog.csdn.net/weixin_43914604/article/details/104943004</a></p>
<ul>
<li>单标志法：<br><img src="https://s2.loli.net/2023/01/04/WZHM1DObSBePoXx.png" alt=""></li>
</ul>
<p><img src="https://s2.loli.net/2023/01/04/DY6NKd8xjkeaT4O.png" alt=""></p>
<ul>
<li>双标志先检查：</li>
</ul>
<p><img src="https://s2.loli.net/2023/01/04/yU67XpsZgwimQSW.png" alt=""></p>
<ul>
<li>双标志后检查：</li>
</ul>
<p><img src="https://s2.loli.net/2023/01/04/9edIMwRyWZqb3mo.png" alt=""></p>
<ul>
<li>Peterson算法（<font color='red'>重要</font>）</li>
</ul>
<p><img src="https://s2.loli.net/2023/01/04/DIKnGZQ9gOLVvJS.png" alt=""></p>
<p>这个算法看似解决了前面算法的所有问题，但是同时也出现了新问题，我们会发现当进程进不去临界区时，一直在while循环里面空耗CPU，这就<font color='red'>违反了让权等待</font>的原则，虽然相较于其他三个算法已经是最好的了，但依然不够好，接下来我们通过硬件来实现。</p>
<h3 id="5-3-硬件实现互斥的方法"><a href="#5-3-硬件实现互斥的方法" class="headerlink" title="5.3 硬件实现互斥的方法"></a>5.3 硬件实现互斥的方法</h3><p>这块同上，图片均来自：<a target="_blank" rel="noopener" href="https://blog.csdn.net/weixin_43914604/article/details/104944962">https://blog.csdn.net/weixin_43914604/article/details/104944962</a></p>
<ul>
<li><h4 id="开关中断"><a href="#开关中断" class="headerlink" title="开关中断"></a>开关中断</h4><p><img src="https://s2.loli.net/2023/01/04/s1QYvLt6a3HWuf8.png" alt=""></p>
</li>
<li><h4 id="Test-and-Set指令实现"><a href="#Test-and-Set指令实现" class="headerlink" title="Test-and-Set指令实现"></a>Test-and-Set指令实现</h4><p>硬件版单标志法，但是由于硬件可以直接在资源上面动刀子，这可比软件带劲。</p>
<p>假设lock现在为false，代表临界资源A空闲，那么我就可以访问这个资源，同时将lock=true，提醒别的进程，这个临界资源A我正在使用，让他们等等</p>
<p>假设lock为true，代表临界资源正在有人使用，所以我必须等待，并且将lock=true，并不影响什么，所以没关系，只是为了让lock为false时可以上锁，将上锁与检查在一个TSL指令完成。</p>
<p><img src="https://s2.loli.net/2023/01/04/AldfWkLJTZiMDGh.png" alt=""></p>
</li>
<li><h4 id="Swap指令"><a href="#Swap指令" class="headerlink" title="Swap指令"></a>Swap指令</h4><p>和TestAndSet指令有一曲同工之妙，甚至连问题都是一样的</p>
<p><img src="https://s2.loli.net/2023/01/04/p7fUPIsZdOy1g8t.png" alt=""></p>
</li>
</ul>
<p>我们发现这几个算法虽然各有千秋，但是都有些的问题：</p>
<ol>
<li>在双标志法中，进入区的“检查”，“上锁”操作无法一起呵成，从而导致同时进临界区或同时进不去的问题。、</li>
<li>所有的解决发难都无法实现“让权等待”</li>
</ol>
<p>这个时候我们隆重介绍我们的重量级选手：信号量机制</p>
<h3 id="5-4-信号量机制"><a href="#5-4-信号量机制" class="headerlink" title="5.4 信号量机制"></a>5.4 信号量机制</h3><p>信号量机制的重点就是wait、signal原语。常称为P、V操作。</p>
<p>接下来看看信号量机制的流程：</p>
<ul>
<li><h4 id="整型信号量（不重要）"><a href="#整型信号量（不重要）" class="headerlink" title="整型信号量（不重要）"></a>整型信号量（<font color='red'>不重要</font>）</h4></li>
</ul>
<p><img src="https://s2.loli.net/2023/01/04/ZiRtLB1FISMmzYo.png" alt=""></p>
<p>整型信号量还是不行，依然解决不了让权等待，再来看看记录型信号量</p>
<ul>
<li><h4 id="记录型信号量"><a href="#记录型信号量" class="headerlink" title="记录型信号量"></a>记录型信号量</h4><p><img src="https://s2.loli.net/2023/01/04/24VIRFjcCMeGvYD.png" alt=""></p>
</li>
</ul>
<p><img src="https://s2.loli.net/2023/01/04/TyZfjb3hCmvzlaP.png" alt=""></p>
<h3 id="5-5-信号量机制实现进程互斥和同步"><a href="#5-5-信号量机制实现进程互斥和同步" class="headerlink" title="5.5 信号量机制实现进程互斥和同步"></a>5.5 信号量机制实现进程互斥和同步</h3><p>我们了解了信号量机制的原理，那我们就大概明白了如何实现进程的互斥。</p>
<p>这也是做题和解决问题最基础的方法。</p>
<ul>
<li><p>实现进程互斥</p>
<ol>
<li>确定临界区</li>
<li>设置互斥信号量，设置处值为1</li>
<li>临界区之前对信号量执行P操作</li>
<li>临界区之后为信号量执行V操作</li>
</ol>
</li>
<li><p>实现进程同步</p>
<ol>
<li>首先找出“一前一后”的关系</li>
<li>设置同步信号量，初始值为0</li>
<li>在“后操作”之后执行V操作</li>
<li>在“前操作”之后执行P操作</li>
</ol>
</li>
<li><p>实现前驱关系</p>
<ol>
<li>画出前驱图，讲每一对前驱关系看成一个同步问题</li>
<li>为每一对前驱关系设置同步信号量</li>
<li>在每个“后操作”之前执行P操作</li>
<li>在每个“前操作”之后执行V操作</li>
</ol>
</li>
</ul>
<p>前驱关系可能不太好理解，前驱关系其实就是一个有向图</p>
<p><img src="https://s2.loli.net/2023/01/09/C8hQdRY4UL7eigr.png" alt=""></p>
<h3 id="5-6-进程同步互斥经典问题"><a href="#5-6-进程同步互斥经典问题" class="headerlink" title="5.6 进程同步互斥经典问题"></a>5.6 进程同步互斥经典问题</h3><h4 id="1-生产者-消费者问题"><a href="#1-生产者-消费者问题" class="headerlink" title="(1)生产者-消费者问题"></a>(1)生产者-消费者问题</h4><ul>
<li>系统中有<code>一组生产者进程</code>和<code>一组消费者进程</code>，生产者进程每次<code>生产一个</code>产品放入缓冲区，消费者进程每次从缓冲区中<code>取出一个</code>产品并使用。(注: 这里的“产品”理解为某种数据)</li>
<li>生产者、消费者<code>共享</code>一个初始为空、大小为n的<code>缓冲区</code>。</li>
<li>只有缓冲区<code>没满</code>时，<code>生产者</code>才能把产品<code>放入</code>缓冲区，否则必须等待。</li>
<li>只有缓冲区<code>不空</code>时，<code>消费者</code>才能从中<code>取出</code>产品，否则必须等待。</li>
<li>缓冲区是临界资源，各进程必须<code>互斥</code>地访问。</li>
</ul>
<p>分析：生产者和消费者对缓冲区互斥访问是<code>互斥关系</code>，同时生产者和消费者又有前后关系，所以他们也是同步关系，而且还是两个同步关系。分别是有空才能放，不空才能取。那么我们就需要三个信号量。</p>
<p><img src="https://s2.loli.net/2023/01/09/WoVeiuNvMw7d38Q.png" alt=""></p>
<p><strong>重点</strong>：实现互斥的P操作一定要在实现同步的P操作之后，否则会造成死锁。V操作则不受限制。</p>
<p>理由：假设我们缓冲区满了，这个时候生产者决定写入进程，于是先将通过P操作进入临界区，结果在临界区发现缓冲区满了，于是进行阻塞，切换到消费者，因为生产者并没有通过V操作释放缓冲区，所以消费者也没法进入缓冲区进行消费，此时两个进程均处于阻塞，均需要对方的资源，导致死锁。</p>
<h4 id="1-1-多生产者-多消费者问题"><a href="#1-1-多生产者-多消费者问题" class="headerlink" title="(1.1)多生产者-多消费者问题"></a>(1.1)多生产者-多消费者问题</h4><p><img src="https://s2.loli.net/2023/01/09/TB4f6OmlFDVN2de.png" alt=""></p>
<p>问题分析：首先可以确定的是对于盘子这个缓冲区的访问一定是互斥的，只有父亲放苹果儿子才能吃，所以这是一对同步关系，只有母亲放橘子女儿才能吃，这又是一对同步关系，只有盘子为空时，父亲或者母亲才能放水果，这又是一对同步关系，与是我们可以定义四个信号量。</p>
<p><img src="https://s2.loli.net/2023/01/09/P4HjFV7JWiwD9BE.png" alt=""></p>
<p>其实本题是个特殊案例，因为缓冲区只有1，所以即使没有mutex实现互斥，apple，orange，plate之中也只会有一个是1，从而进入临界区，一旦缓冲区变成2，那么就必须要mutex实现互斥了，否则可能会造成覆盖。</p>
<h4 id="2-读者写者问题"><a href="#2-读者写者问题" class="headerlink" title="(2)读者写者问题"></a>(2)读者写者问题</h4><p><img src="https://s2.loli.net/2023/01/10/xqMaI8vho67Ufcy.png" alt=""></p>
<p>问题分析：写者与写者之间一定是互斥关系，写者与读者之间也一定是互斥关系。但是如果我们直接使用一个信号量处理读者和写者之间的互斥关系就会造成读者和读者之间发生互斥，这不是我们想看到的，所以我们需要一个特殊处理。</p>
<p>首先未来解决读者与读者不互斥，而读者和写者互斥，我们引入一个count变量，这个变量用于记录正在读取的变量，如国count等于0，则说明本进程是第一个访问的变量，这个时候给临界区使用P操作，然后使count++，最后退出的时候再次检测count，若count=0则自己是最后一个读进程，使用V操作进行解锁。这样就可以保证写进程和读进程的互斥，又能保证读进程之间不影响。</p>
<p><img src="https://s2.loli.net/2023/01/10/9vuaDQBlNnobxYf.png" alt=""></p>
<p>但是这有一个潜藏的隐患，假设写者1在运行到P(rw)的时候，突然遭遇进程切换，切换到了写者2，由于写者1还未运行到count++，所以count现在依旧是0，所以写者2执行P(rw)，由于写者1未执行V(rw)所以阻塞，这样的话就不满足读者与读者之间互相不干扰的条件，引起这种情况的原因主要是对于count的检测与操作并不能确保互斥，那怎样保证互斥呢？没错，我们使用信号量就是为了保证互斥性，所以我们引入一个信号量用于保证互斥性</p>
<p><img src="https://s2.loli.net/2023/01/10/nckNgCZfO7IJAe4.png" alt=""></p>
<p>正如图中所说，只要一直有读进程进入，那么rw一直不被释放，那么就会导致写进程一直阻塞等待，可能会导致“饿死”，这是我们不想看到的，所以我们希望当写进程要开始写的时候就不要让count继续增加了，所以我们需要让count增加的代码和写进程的写代码互斥。我们再次引入一个信号量进行互斥控制</p>
<p><img src="https://s2.loli.net/2023/01/10/PdFxtjOT2ArKGas.png" alt="20200326221227585"></p>
<p>这个问题的核心思想设置了一个计数器<font color='red'>count用来记录当前正在访问共享文件的读进程数</font>以及用<font color='red'>互斥信号量解决无法“一气呵成”的代码</font></p>
<h4 id="3-吸烟者问题"><a href="#3-吸烟者问题" class="headerlink" title="(3)吸烟者问题"></a>(3)吸烟者问题</h4><p><img src="https://s2.loli.net/2023/01/10/7dHPFQfpusAtmSk.png" alt=""></p>
<p>问题分析：所有这种问题，第一步都是找关系，首先对于桌子的访问一定互斥的，然后只有供应者提供抽烟者1需要的素材，抽烟者1才能取走东西，这是一个同步关系，以此类推，可以推出三个同步关系，第三点就是吸烟者发出信号告诉供应者供应者才能将下一个组合放到桌上。</p>
<p>当然对于这个题，我们的桌子只有1，所以也没必要设置一个专门的互斥信号量进行互斥操作。</p>
<p>那如何实现轮流呢，我们可以使用一个数来表示需要提供谁的东西，并且每次提供后对i=(i+1)%3，这样就能保证循环了。</p>
<p><img src="https://s2.loli.net/2023/01/10/oJflm3bgO4NkETu.png" alt=""></p>
<p>这个问题主要了解到可以用一个整形变量i来实现轮流的过程。</p>
<h4 id="4-哲学家进餐问题"><a href="#4-哲学家进餐问题" class="headerlink" title="(4)哲学家进餐问题"></a>(4)哲学家进餐问题</h4><p><img src="https://s2.loli.net/2023/01/11/w2NzyafVkEqpK5T.png" alt=""></p>
<p>问题分析：本题没有同步关系，每两个人之间的筷子相对于这两个人应该是互斥访问的，那我们使用五个互斥信号量尝试一下。</p>
<p><img src="https://s2.loli.net/2023/01/11/UCA2NelyHbXrZFj.png" alt=""></p>
<p>我们来讨论一下为什么单纯使用五个互斥变量不行，假设进程1在对左边的筷子的时候执行了P操作而这时候遇上进程切换进程2也同时对左边的筷子进行P操作，依次进行下去，所有人都拿到了一根筷子，然后也都等着其他进程把筷子让出来，这就导致了死锁，这当然不是我们想看到的，而想要解决这个问题我们有许多方法。比如我们可以设下条件，最多同时有四个人进入临界区，那么至少有一个人能够获得两根筷子，或者我们可以限定奇数的先拿左边的筷子，偶数的先拿右边的筷子，这样也能避免死锁，但是这些实现方案都太过复杂了。</p>
<p>我们重新分析为什么为什么我们之前的方法不行，因为我们在拿完左边的筷子的时候可能因为进程切换我们拿不到右边的筷子，这个问题归根结底就是取左边筷子和右边筷子不能“一气呵成”，我们前面已经多次遇到了不能一气呵成的代码的解决方式，没错我们再引入一个互斥信号量，确保拿左边筷子和拿右边筷子可以一气呵成的完成。那我们就得到了下面的代码。</p>
<p><img src="C:\Users\cy\Desktop\20200326231222488.png" alt=""></p>
<p>哲学家问题给我们提供了一个方案解决可能导致的死锁的问题，通过一个互斥信号量保证每一个进程取所需要的东西时不会被打断。</p>
<h3 id="5-7-管程"><a href="#5-7-管程" class="headerlink" title="5.7 管程"></a>5.7 管程</h3><p>之前我们介绍了信号量机制，也用他解决了非常多的进程同步相关的问题，但是我们能明显的发现一个问题，就是这个信号量同步机制，如果全都由程序员编程来实现的话实在是太复杂了，于是Brinch Hansen首次在程序设计语言（Pascal）中引入了“管程”成分。</p>
<p>管程的组成：</p>
<ol>
<li>局部于管程的共享数据结构说明</li>
<li>对该数据结构进行操作的一组过程</li>
<li>对局部于管程的共享数据设置初始值的语句</li>
<li>管程有一个名字</li>
</ol>
<p>管程的基本特征：</p>
<ol>
<li>局部于管程的数据只能被局部于管程的过程所访问</li>
<li>一个进程只有通过调用管程内的过程才能进入管程访问数据结构</li>
<li>每次仅允许一个进程在管程内执行某个内部过程</li>
</ol>
<p>各大高级语言都有管程的实现方式，具体的使用和实现可以自己去寻找官方文档或者自行搜索。</p>
<p>看起来这个管程的组成和特征比较难理解，但其实我们可以使用高级编程语言的方式来理解：</p>
<p>我们把管程看做是一个类，这个类中有一个私有的数据结构，只能通过这个类内部的实现的方法进行访问和修改，然后这个类定义了很多很多的方法确保能够访问数据结构。并且这个类每次都只允许一个进程进入使用里面的方法对这个数据结构进行操作，从而确保同步或者互斥访问。</p>
<h3 id="5-8-死锁"><a href="#5-8-死锁" class="headerlink" title="5.8 死锁"></a>5.8 死锁</h3><h4 id="1-死锁的定义"><a href="#1-死锁的定义" class="headerlink" title="(1)死锁的定义"></a>(1)死锁的定义</h4><p>各进程之间互相等待对方手里的资源，导致各进程都阻塞，无法向前推进</p>
<p>最典型的例子就是上面提到过的哲学家进餐问题，如果使用最初的版本就可能导致五个人都拿到左边的筷子，这样大伙都在等其他人放下筷子，从而使大伙都阻塞了。</p>
<p>明确三个概念：死锁，饥饿和死循环</p>
<p><img src="https://s2.loli.net/2023/01/11/HxITMzfacEXBUZ1.png" alt=""></p>
<h4 id="2-死锁产生的四个必要条件"><a href="#2-死锁产生的四个必要条件" class="headerlink" title="(2)死锁产生的四个必要条件"></a>(2)死锁产生的四个必要条件</h4><ul>
<li>互斥条件：对必须互斥使用的资源的抢夺才会导致死锁</li>
<li>不剥夺条件：进程保持的资源只能主动释放，不可强行剥夺</li>
<li>请求和保持条件：保持着某些资源不放的同时，请求别的资源</li>
<li>循环等待条件：存在一种进程资源的循环等待，</li>
</ul>
<p>总结：对于不可剥夺资源的不合理分配，可能造成死锁</p>
<h4 id="3-死锁的解决方案"><a href="#3-死锁的解决方案" class="headerlink" title="(3)死锁的解决方案"></a>(3)死锁的解决方案</h4><p>总体来说分为三个部分：</p>
<ul>
<li><p>预防死锁：破环死锁产生的四个必要条件中的一个或几个。</p>
<ol>
<li><p>破坏互斥条件：如果把只能互斥使用的资源改造未允许共享使用，则系统不会进入死锁状态</p>
<p><img src="https://s2.loli.net/2023/01/11/hGCe1DOrUTPnMou.png" alt=""></p>
</li>
<li><p>破坏不可剥夺原则：</p>
<p>   <img src="https://s2.loli.net/2023/01/11/lEKrkThLjiwIvCd.png" alt=""></p>
</li>
<li><p>破坏请求和保持条件</p>
<p><img src="https://s2.loli.net/2023/01/11/8IAYbga5cJrKDey.png" alt=""></p>
</li>
<li><p>破坏循环等待条件</p>
<p>   <img src="https://s2.loli.net/2023/01/11/H4vQGZbNcLpEPVK.png" alt=""></p>
</li>
</ol>
</li>
<li><p>避免死锁（<font color='red'>银行家算法</font>）（<font color='red'>重点</font>）</p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/Dustinthewine/article/details/125924551">https://blog.csdn.net/Dustinthewine/article/details/125924551</a></p>
</li>
<li><p>死锁的检测和解除</p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/LOOKTOMMER/article/details/121753670">https://blog.csdn.net/LOOKTOMMER/article/details/121753670</a></p>
</li>
</ul>
</div>
        </div>
        
            <div class="kratos-copyright text-center clearfix">
                <h5 itemprop="copyrightNotice">本作品采用 <a rel="license nofollow" target="_blank" href="https://creativecommons.org/licenses/by-sa/4.0/">知识共享署名-相同方式共享 4.0 国际许可协议</a> 进行许可</h5>
            </div>
        
        <footer class="kratos-entry-footer clearfix">
            
                <div class="post-like-donate text-center clearfix" id="post-like-donate">
                
                
                    <a class="share" href="javascript:;"><i class="fa fa-share-alt"></i> 分享</a>
                    <div class="share-wrap" style="display: none;">
    <div class="share-group">
        <a href="javascript:;" class="share-plain qq" onclick="share('qq');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-qq"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain qzone" onclick="share('qzone');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-star"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain weixin pop style-plain" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-weixin"></i>
            </div>
            <div class="share-int">
                <div class="qrcode" id="wechat-qr"></div>
                <p>打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮</p>
            </div>
        </a>
        <a href="javascript:;" class="share-plain weibo" onclick="share('weibo');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-weibo"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain facebook style-plain" onclick="share('facebook');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-facebook"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain twitter style-plain" onclick="share('twitter');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-twitter"></i>
            </div>
        </a>
    </div>
    <script type="text/javascript">
        $(()=>{
            new QRCode("wechat-qr", {
                text: "http://example.com/2023/01/04/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0-5/",
                width: 150,
                height: 150,
                correctLevel : QRCode.CorrectLevel.H
            });
        });
        function share(dest) {
            const qqBase        = "https://connect.qq.com/widget/shareqq/index.html?";
            const weiboBase     = "https://service.weibo.com/share/share.php?";
            const qzoneBase     = "https://sns.qzone.qq.com/cgi-bin/qzshare/cgi_qzshare_onekey?";
            const facebookBase  = "https://www.facebook.com/sharer/sharer.php?";
            const twitterBase   = "https://twitter.com/intent/tweet?";
            const hostUrl       = "http://example.com/2023/01/04/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0-5/";
            const title         = "「进程同步与互斥（操作系统笔记5）」";
            const excerpt       = `本篇笔记将介绍一下进程的同步与互斥，由于进程的异步性会产生非常多的包括死锁等问题。本章主要讲述如何处理或解决这些问题。`;
            let _URL;
            switch (dest) {
                case "qq"       : _URL = qqBase+"url="+hostUrl+"&title="+title+"&desc=&summary="+excerpt+"&site=cxpy";     break;
                case "weibo"    : _URL = weiboBase+"url="+hostUrl+"&title="+title+excerpt;                                 break;
                case "qzone"    : _URL = qzoneBase+"url="+hostUrl+"&title="+title+"&desc=&summary="+excerpt+"&site=cxpy";  break;
                case "facebook" : _URL = facebookBase+"u="+hostUrl;                                                        break;
                case "twitter"  : _URL = twitterBase+"text="+title+excerpt+"&url="+hostUrl;                                break;
            }
            window.open(_URL);
        };
    </script>
</div>
                
                </div>
            
            <div class="footer-tag clearfix">
                <div class="pull-left">
                <i class="fa fa-tags"></i>
                    <a class="tag-none-link" href="/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" rel="tag">操作系统</a>
                </div>
                <div class="pull-date">
                    <time datetime="2023-02-13T06:16:33.855Z" itemprop="dateModified">最后编辑：2023-02-13</time>
                </div>
            </div>
        </footer>
    </div>
    
        <nav class="navigation post-navigation clearfix" role="navigation">
            
            <div class="nav-previous clearfix">
                <a title=" 处理机调度（操作系统笔记4）" href="/2023/01/02/操作系统笔记/操作系统笔记-4/">&lt; 上一篇</a>
            </div>
            
            
            <div class="nav-next clearfix">
                <a title=" 内存管理（操作系统笔记6）" href="/2023/01/12/操作系统笔记/操作系统笔记-6/">下一篇 &gt;</a>
            </div>
            
        </nav>
    
    
</article>

        

            </section>

        

                
            

<section id="kratos-widget-area" class="col-md-4 hidden-xs hidden-sm">
    <!-- 文章和页面根据splitter来分割，没有的话就从头开始设置为sticky -->
    
    
                <aside id="krw-about" class="widget widget-kratos-about clearfix">
    <div class="photo-background"></div>
    <div class="photo-wrapper clearfix">
        <div class="photo-wrapper-tip text-center">
            <img class="about-photo" src="/images/avatar.webp" loading="lazy" decoding="auto" />
        </div>
    </div>
    <div class="textwidget">
        <p class="text-center"></p>
    </div>
    <div class="site-meta">
        <a class="meta-item" href="/archives/">
            <span class="title">
                文章
            </span>
            <span class="count">
                39
            </span>
        </a>
        <a class="meta-item" href="/categories/">
            <span class="title">
                分类
            </span>
            <span class="count">
                7
            </span>
        </a>
        <a class="meta-item" href="/tags/">
            <span class="title">
                标签
            </span>
            <span class="count">
                10
            </span>
        </a>
    </div>
</aside>
            
                    <div class="sticky-area">
                
                
  <aside id="krw-categories" class="widget widget-kratos-categories clearfix">
    <h4 class="widget-title"><i class="fa fa-folder"></i>分类目录</h4>
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/C-%E7%9F%A5%E8%AF%86/">C#知识</a><span class="category-list-count">9</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/Lua/">Lua</a><span class="category-list-count">10</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/Unity%E7%BD%91%E7%BB%9C%E6%B8%B8%E6%88%8F%E5%BC%80%E5%8F%91/">Unity网络游戏开发</a><span class="category-list-count">3</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B4/">宝可梦小说</a><span class="category-list-count">5</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0/">操作系统笔记</a><span class="category-list-count">10</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AC%94%E8%AE%B0/">数据结构笔记</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E9%9A%8F%E6%83%B3/">随想</a><span class="category-list-count">1</span></li></ul>
  </aside>


            
                
  <aside id="krw-tags" class="widget widget-kratos-tags clearfix">
    <h4 class="widget-title"><i class="fa fa-tags"></i>标签聚合</h4>
      <div class="tag-clouds">
        <a href="/tags/C/" style="font-size: 0.75em;">C#</a> <a href="/tags/Lua/" style="font-size: 0.8em;">Lua</a> <a href="/tags/unity/" style="font-size: 0.65em;">unity</a> <a href="/tags/%E5%AE%9D%E5%8F%AF%E6%A2%A6/" style="font-size: 0.7em;">宝可梦</a> <a href="/tags/%E5%BD%B1%E8%AF%84/" style="font-size: 0.6em;">影评</a> <a href="/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" style="font-size: 0.8em;">操作系统</a> <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="font-size: 0.6em;">数据结构</a> <a href="/tags/%E7%AE%97%E6%B3%95/" style="font-size: 0.6em;">算法</a> <a href="/tags/%E7%BD%91%E7%BB%9C%E6%B8%B8%E6%88%8F/" style="font-size: 0.65em;">网络游戏</a> <a href="/tags/%E9%9A%8F%E6%83%B3/" style="font-size: 0.6em;">随想</a>
      </div>
  </aside>

            
                
  <aside id="krw-posts" class="widget widget-kratos-posts">
  <h4 class="widget-title"><i class="fa fa-file"></i>最新文章</h4>
  <div class="tab-content">
      <ul class="list-group">
        
        
          
          
            <a class="list-group-item" href="/2025/10/08/%E9%9A%8F%E6%83%B3/%E3%80%8A%E6%98%9F%E4%B8%89%E5%9B%BD%E3%80%8B%E5%90%90%E6%A7%BD/"><i class="fa  fa-book"></i> 《星三国》吐槽</a>
            
          
        
          
          
            <a class="list-group-item" href="/2023/08/14/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B4/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B45/"><i class="fa  fa-book"></i> 宝可梦小说第五章</a>
            
          
        
          
          
            <a class="list-group-item" href="/2023/08/13/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B4/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B44/"><i class="fa  fa-book"></i> 宝可梦小说第四章</a>
            
          
        
          
          
            <a class="list-group-item" href="/2023/08/10/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B4/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B43/"><i class="fa  fa-book"></i> 宝可梦小说第三章</a>
            
          
        
          
          
            <a class="list-group-item" href="/2023/08/09/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B4/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B42/"><i class="fa  fa-book"></i> 宝可梦小说第二章</a>
            
          
        
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
      </ul>
  </div>
  </aside>

            
    </div>
</section>
        
        </div>
    </div>
</div>
<footer>
    <div id="footer"  >
        <div class="container">
            <div class="row">
                <div class="col-md-6 col-md-offset-3 footer-list text-center">
                    <ul class="kratos-social-icons">
                        
                        
                        
                        
                        
                        
                        
                        
                        
                    </ul>
                    <ul class="kratos-copyright">
                        <div>
                            <li>&copy; 2025 舛羽的笔记小站 版权所有.</li>
                            <li>本站已运行<span id="span_dt">Loading...</span></li>
                        </div>
                        <div>
                            <li>Theme <a href="https://github.com/Candinya/Kratos-Rebirth" target="_blank">Kratos:Rebirth</a></li>
                            <li>Site built with&nbsp;<i class="fa fa-heart throb" style="color:#d43f57"></i>&nbsp;by cy.</li>
                        </div>
                        <div>
                            <li>Powered by <a href="https://hexo.io" target="_blank" rel="nofollow">Hexo</a></li>
                            <li>Hosted on <a href="https://github.io" target="_blank">Github Pages</a></li>
                        </div>
                        <div>
                            
                            
                        </div>
                    </ul>
                </div>
            </div>
        </div>
        <div class="kr-tool text-center">
            <div class="tool">
                
                    <div class="box search-box">
                        <a href="/search/">
                            <span class="fa fa-search"></span>
                        </a>
                    </div>
                
                
                    <div class="box theme-box" id="darkmode-switch">
                        <span class="fa fa-adjust"></span>
                    </div>
                
                
            </div>
            <div class="box gotop-box">
                <span class="fa fa-chevron-up"></span>
            </div>
        </div>
    </div>
</footer>
</div>
</div>

        <script defer src="/vendors/bootstrap@3.3.4/dist/js/bootstrap.min.js"></script>
<script defer src="/vendors/nprogress@0.2.0/nprogress.js"></script>
<script>
    if (!window.kr) {
        window.kr = {};
    }
    window.kr.notMobile = (!(navigator.userAgent.match(/(phone|pad|pod|iPhone|iPod|ios|iPad|Android|Mobile|BlackBerry|IEMobile|MQQBrowser|JUC|Fennec|wOSBrowser|BrowserNG|WebOS|Symbian|Windows Phone)/i)));
    window.kr.siteRoot = "/";
</script>


    <script async src="/js/candy.min.js"></script>




    <script defer src="/vendors/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js"></script>

<script defer src="/vendors/clipboard@2.0.6/dist/clipboard.min.js"></script>
<script defer src="/js/kratosr.min.js"></script>
<script defer src="/js/pjax.min.js"></script>



<!-- Extra support for third-party plguins  -->


    <script type="text/x-mathjax-config">
    MathJax.Hub.Config({
        tex2jax: {
            inlineMath: [ ["$","$"], ["\\(","\\)"] ],
            skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code'],
            processEscapes: true
        }
    });
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax();
        for (var i = 0; i < all.length; ++i)
            all[i].SourceElement().parentNode.className += ' has-jax';
    });
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-MML-AM_CHTML
"></script>
</body>
</html>